# 给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
#
#  具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
#
#
#
#  示例 1：
#
#  输入："abc"
# 输出：3
# 解释：三个回文子串: "a", "b", "c"
#
#
#  示例 2：
#
#  输入："aaa"
# 输出：6
# 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
#
#
#
#  提示：
#
#
#  输入的字符串长度不会超过 1000 。
#
#  Related Topics 字符串 动态规划
#  👍 367 👎 0


# leetcode submit region begin(Prohibit modification and deletion)
class Solution(object):
    def countSubstrings(self, s):
        # 列出所有的回文中心，一遍循环统一奇数和偶数的情况

        # 0	0	0
        # 1	0	1
        # 2	1	1
        # 3	1	2
        # 4	2	2
        # 5	2	3
        # 6	3	3

        n = len(s)

        count = 0

        for k in range(0, 2 * n - 1):
            l, r = k // 2, k // 2 + k % 2

            while l >= 0 and r < n and s[l] == s[r]:
                count += 1
                l -= 1
                r += 1

        return count

    # leetcode submit region end(Prohibit modification and deletion)


print(Solution().countSubstrings("aba"))
